core/iter/traits/double_ended.rs
1use crate::array;
2use crate::marker::Destruct;
3use crate::num::NonZero;
4use crate::ops::{ControlFlow, Try};
5
6/// An iterator able to yield elements from both ends.
7///
8/// Something that implements `DoubleEndedIterator` has one extra capability
9/// over something that implements [`Iterator`]: the ability to also take
10/// `Item`s from the back, as well as the front.
11///
12/// It is important to note that both back and forth work on the same range,
13/// and do not cross: iteration is over when they meet in the middle.
14///
15/// In a similar fashion to the [`Iterator`] protocol, once a
16/// `DoubleEndedIterator` returns [`None`] from a [`next_back()`], calling it
17/// again may or may not ever return [`Some`] again. [`next()`] and
18/// [`next_back()`] are interchangeable for this purpose.
19///
20/// [`next_back()`]: DoubleEndedIterator::next_back
21/// [`next()`]: Iterator::next
22///
23/// # Examples
24///
25/// Basic usage:
26///
27/// ```
28/// let numbers = vec![1, 2, 3, 4, 5, 6];
29///
30/// let mut iter = numbers.iter();
31///
32/// assert_eq!(Some(&1), iter.next());
33/// assert_eq!(Some(&6), iter.next_back());
34/// assert_eq!(Some(&5), iter.next_back());
35/// assert_eq!(Some(&2), iter.next());
36/// assert_eq!(Some(&3), iter.next());
37/// assert_eq!(Some(&4), iter.next());
38/// assert_eq!(None, iter.next());
39/// assert_eq!(None, iter.next_back());
40/// ```
41#[stable(feature = "rust1", since = "1.0.0")]
42#[rustc_diagnostic_item = "DoubleEndedIterator"]
43#[rustc_const_unstable(feature = "const_iter", issue = "92476")]
44pub const trait DoubleEndedIterator: [const] Iterator {
45 /// Removes and returns an element from the end of the iterator.
46 ///
47 /// Returns `None` when there are no more elements.
48 ///
49 /// The [trait-level] docs contain more details.
50 ///
51 /// [trait-level]: DoubleEndedIterator
52 ///
53 /// # Examples
54 ///
55 /// Basic usage:
56 ///
57 /// ```
58 /// let numbers = vec![1, 2, 3, 4, 5, 6];
59 ///
60 /// let mut iter = numbers.iter();
61 ///
62 /// assert_eq!(Some(&1), iter.next());
63 /// assert_eq!(Some(&6), iter.next_back());
64 /// assert_eq!(Some(&5), iter.next_back());
65 /// assert_eq!(Some(&2), iter.next());
66 /// assert_eq!(Some(&3), iter.next());
67 /// assert_eq!(Some(&4), iter.next());
68 /// assert_eq!(None, iter.next());
69 /// assert_eq!(None, iter.next_back());
70 /// ```
71 ///
72 /// # Remarks
73 ///
74 /// The elements yielded by `DoubleEndedIterator`'s methods may differ from
75 /// the ones yielded by [`Iterator`]'s methods:
76 ///
77 /// ```
78 /// let vec = vec![(1, 'a'), (1, 'b'), (1, 'c'), (2, 'a'), (2, 'b')];
79 /// let uniq_by_fst_comp = || {
80 /// let mut seen = std::collections::HashSet::new();
81 /// vec.iter().copied().filter(move |x| seen.insert(x.0))
82 /// };
83 ///
84 /// assert_eq!(uniq_by_fst_comp().last(), Some((2, 'a')));
85 /// assert_eq!(uniq_by_fst_comp().next_back(), Some((2, 'b')));
86 ///
87 /// assert_eq!(
88 /// uniq_by_fst_comp().fold(vec![], |mut v, x| {v.push(x); v}),
89 /// vec![(1, 'a'), (2, 'a')]
90 /// );
91 /// assert_eq!(
92 /// uniq_by_fst_comp().rfold(vec![], |mut v, x| {v.push(x); v}),
93 /// vec![(2, 'b'), (1, 'c')]
94 /// );
95 /// ```
96 #[stable(feature = "rust1", since = "1.0.0")]
97 fn next_back(&mut self) -> Option<Self::Item>;
98
99 /// Advances from the back of the iterator and returns an array containing the next
100 /// `N` values in sequence.
101 ///
102 /// If there are not enough elements to fill the array then `Err` is returned
103 /// containing an iterator over the remaining elements.
104 ///
105 /// Note: This is not equivalent to doing `iter.rev().next_chunk()` as this method
106 /// takes elements from the back of the iterator and preserves the order that the
107 /// elements were seen in the original iterator.
108 ///
109 /// # Examples
110 ///
111 /// Basic usage:
112 ///
113 /// ```
114 /// #![feature(iter_next_chunk)]
115 ///
116 /// let mut iter = "lorem".chars();
117 ///
118 /// assert_eq!(iter.next_chunk_back().unwrap(), ['e', 'm']); // N is inferred as 2
119 /// assert_eq!(iter.next_chunk_back().unwrap(), ['l', 'o', 'r']); // N is inferred as 3
120 /// assert_eq!(iter.next_chunk_back::<4>().unwrap_err().as_slice(), &[]); // N is explicitly 4
121 /// ```
122 ///
123 /// Split a string and get the last three items in sequence.
124 ///
125 /// ```
126 /// #![feature(iter_next_chunk)]
127 ///
128 /// let quote = "not all those who wander are lost";
129 /// let [first, second, third] = quote.split_whitespace().next_chunk_back().unwrap();
130 /// assert_eq!(first, "wander");
131 /// assert_eq!(second, "are");
132 /// assert_eq!(third, "lost");
133 /// ```
134 #[inline]
135 #[unstable(feature = "iter_next_chunk", issue = "98326")]
136 #[rustc_non_const_trait_method]
137 fn next_chunk_back<const N: usize>(
138 &mut self,
139 ) -> Result<[Self::Item; N], array::IntoIter<Self::Item, N>>
140 where
141 Self: Sized,
142 {
143 crate::array::iter_next_chunk_back(self)
144 }
145
146 /// Advances the iterator from the back by `n` elements.
147 ///
148 /// `advance_back_by` is the reverse version of [`advance_by`]. This method will
149 /// eagerly skip `n` elements starting from the back by calling [`next_back`] up
150 /// to `n` times until [`None`] is encountered.
151 ///
152 /// `advance_back_by(n)` will return `Ok(())` if the iterator successfully advances by
153 /// `n` elements, or a `Err(NonZero<usize>)` with value `k` if [`None`] is encountered, where `k`
154 /// is remaining number of steps that could not be advanced because the iterator ran out.
155 /// If `self` is empty and `n` is non-zero, then this returns `Err(n)`.
156 /// Otherwise, `k` is always less than `n`.
157 ///
158 /// Calling `advance_back_by(0)` can do meaningful work, for example [`Flatten`] can advance its
159 /// outer iterator until it finds an inner iterator that is not empty, which then often
160 /// allows it to return a more accurate `size_hint()` than in its initial state.
161 ///
162 /// [`advance_by`]: Iterator::advance_by
163 /// [`Flatten`]: crate::iter::Flatten
164 /// [`next_back`]: DoubleEndedIterator::next_back
165 ///
166 /// # Examples
167 ///
168 /// Basic usage:
169 ///
170 /// ```
171 /// #![feature(iter_advance_by)]
172 ///
173 /// use std::num::NonZero;
174 ///
175 /// let a = [3, 4, 5, 6];
176 /// let mut iter = a.iter();
177 ///
178 /// assert_eq!(iter.advance_back_by(2), Ok(()));
179 /// assert_eq!(iter.next_back(), Some(&4));
180 /// assert_eq!(iter.advance_back_by(0), Ok(()));
181 /// assert_eq!(iter.advance_back_by(100), Err(NonZero::new(99).unwrap())); // only `&3` was skipped
182 /// ```
183 ///
184 /// [`Ok(())`]: Ok
185 /// [`Err(k)`]: Err
186 #[inline]
187 #[unstable(feature = "iter_advance_by", issue = "77404")]
188 fn advance_back_by(&mut self, n: usize) -> Result<(), NonZero<usize>>
189 where
190 Self::Item: [const] Destruct,
191 {
192 /// Helper trait to specialize `advance_back_by` via `try_rfold` for `Sized` iterators.
193
194 #[rustc_const_unstable(feature = "const_iter", issue = "92476")]
195 const trait SpecAdvanceBackBy {
196 fn spec_advance_back_by(&mut self, n: usize) -> Result<(), NonZero<usize>>;
197 }
198
199 #[rustc_const_unstable(feature = "const_iter", issue = "92476")]
200 const impl<I: [const] DoubleEndedIterator + ?Sized> SpecAdvanceBackBy for I
201 where
202 I::Item: [const] Destruct,
203 {
204 default fn spec_advance_back_by(&mut self, n: usize) -> Result<(), NonZero<usize>> {
205 for i in 0..n {
206 if self.next_back().is_none() {
207 // SAFETY: `i` is always less than `n`.
208 return Err(unsafe { NonZero::new_unchecked(n - i) });
209 }
210 }
211 Ok(())
212 }
213 }
214
215 #[rustc_const_unstable(feature = "const_iter", issue = "92476")]
216 const impl<I: [const] DoubleEndedIterator> SpecAdvanceBackBy for I
217 where
218 I::Item: [const] Destruct,
219 {
220 fn spec_advance_back_by(&mut self, n: usize) -> Result<(), NonZero<usize>> {
221 let Some(n) = NonZero::new(n) else {
222 return Ok(());
223 };
224
225 let res = self.try_rfold(n, const |n, _| NonZero::new(n.get() - 1));
226
227 match res {
228 None => Ok(()),
229 Some(n) => Err(n),
230 }
231 }
232 }
233
234 self.spec_advance_back_by(n)
235 }
236
237 /// Returns the `n`th element from the end of the iterator.
238 ///
239 /// This is essentially the reversed version of [`Iterator::nth()`].
240 /// Although like most indexing operations, the count starts from zero, so
241 /// `nth_back(0)` returns the first value from the end, `nth_back(1)` the
242 /// second, and so on.
243 ///
244 /// Note that all elements between the end and the returned element will be
245 /// consumed, including the returned element. This also means that calling
246 /// `nth_back(0)` multiple times on the same iterator will return different
247 /// elements.
248 ///
249 /// `nth_back()` will return [`None`] if `n` is greater than or equal to the
250 /// length of the iterator.
251 ///
252 /// # Examples
253 ///
254 /// Basic usage:
255 ///
256 /// ```
257 /// let a = [1, 2, 3];
258 /// assert_eq!(a.iter().nth_back(2), Some(&1));
259 /// ```
260 ///
261 /// Calling `nth_back()` multiple times doesn't rewind the iterator:
262 ///
263 /// ```
264 /// let a = [1, 2, 3];
265 ///
266 /// let mut iter = a.iter();
267 ///
268 /// assert_eq!(iter.nth_back(1), Some(&2));
269 /// assert_eq!(iter.nth_back(1), None);
270 /// ```
271 ///
272 /// Returning `None` if there are less than `n + 1` elements:
273 ///
274 /// ```
275 /// let a = [1, 2, 3];
276 /// assert_eq!(a.iter().nth_back(10), None);
277 /// ```
278 #[inline]
279 #[stable(feature = "iter_nth_back", since = "1.37.0")]
280 fn nth_back(&mut self, n: usize) -> Option<Self::Item>
281 where
282 Self::Item: [const] Destruct,
283 {
284 self.advance_back_by(n).ok()?;
285 self.next_back()
286 }
287
288 /// This is the reverse version of [`Iterator::try_fold()`]: it takes
289 /// elements starting from the back of the iterator.
290 ///
291 /// # Examples
292 ///
293 /// Basic usage:
294 ///
295 /// ```
296 /// let a = ["1", "2", "3"];
297 /// let sum = a.iter()
298 /// .map(|&s| s.parse::<i32>())
299 /// .try_rfold(0, |acc, x| x.and_then(|y| Ok(acc + y)));
300 /// assert_eq!(sum, Ok(6));
301 /// ```
302 ///
303 /// Short-circuiting:
304 ///
305 /// ```
306 /// let a = ["1", "rust", "3"];
307 /// let mut it = a.iter();
308 /// let sum = it
309 /// .by_ref()
310 /// .map(|&s| s.parse::<i32>())
311 /// .try_rfold(0, |acc, x| x.and_then(|y| Ok(acc + y)));
312 /// assert!(sum.is_err());
313 ///
314 /// // Because it short-circuited, the remaining elements are still
315 /// // available through the iterator.
316 /// assert_eq!(it.next_back(), Some(&"1"));
317 /// ```
318 #[inline]
319 #[stable(feature = "iterator_try_fold", since = "1.27.0")]
320 fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R
321 where
322 Self: Sized,
323 F: [const] FnMut(B, Self::Item) -> R + [const] Destruct,
324 R: [const] Try<Output = B>,
325 {
326 let mut accum = init;
327 while let Some(x) = self.next_back() {
328 accum = f(accum, x)?;
329 }
330 try { accum }
331 }
332
333 /// An iterator method that reduces the iterator's elements to a single,
334 /// final value, starting from the back.
335 ///
336 /// This is the reverse version of [`Iterator::fold()`]: it takes elements
337 /// starting from the back of the iterator.
338 ///
339 /// `rfold()` takes two arguments: an initial value, and a closure with two
340 /// arguments: an 'accumulator', and an element. The closure returns the value that
341 /// the accumulator should have for the next iteration.
342 ///
343 /// The initial value is the value the accumulator will have on the first
344 /// call.
345 ///
346 /// After applying this closure to every element of the iterator, `rfold()`
347 /// returns the accumulator.
348 ///
349 /// This operation is sometimes called 'reduce' or 'inject'.
350 ///
351 /// Folding is useful whenever you have a collection of something, and want
352 /// to produce a single value from it.
353 ///
354 /// Note: `rfold()` combines elements in a *right-associative* fashion. For associative
355 /// operators like `+`, the order the elements are combined in is not important, but for non-associative
356 /// operators like `-` the order will affect the final result.
357 /// For a *left-associative* version of `rfold()`, see [`Iterator::fold()`].
358 ///
359 /// # Examples
360 ///
361 /// Basic usage:
362 ///
363 /// ```
364 /// let a = [1, 2, 3];
365 ///
366 /// // the sum of all of the elements of a
367 /// let sum = a.iter()
368 /// .rfold(0, |acc, &x| acc + x);
369 ///
370 /// assert_eq!(sum, 6);
371 /// ```
372 ///
373 /// This example demonstrates the right-associative nature of `rfold()`:
374 /// it builds a string, starting with an initial value
375 /// and continuing with each element from the back until the front:
376 ///
377 /// ```
378 /// let numbers = [1, 2, 3, 4, 5];
379 ///
380 /// let zero = "0".to_string();
381 ///
382 /// let result = numbers.iter().rfold(zero, |acc, &x| {
383 /// format!("({x} + {acc})")
384 /// });
385 ///
386 /// assert_eq!(result, "(1 + (2 + (3 + (4 + (5 + 0)))))");
387 /// ```
388 #[doc(alias = "foldr")]
389 #[inline]
390 #[stable(feature = "iter_rfold", since = "1.27.0")]
391 fn rfold<B, F>(mut self, init: B, mut f: F) -> B
392 where
393 Self: Sized + [const] Destruct,
394 F: [const] FnMut(B, Self::Item) -> B + [const] Destruct,
395 {
396 let mut accum = init;
397 while let Some(x) = self.next_back() {
398 accum = f(accum, x);
399 }
400 accum
401 }
402
403 /// Searches for an element of an iterator from the back that satisfies a predicate.
404 ///
405 /// `rfind()` takes a closure that returns `true` or `false`. It applies
406 /// this closure to each element of the iterator, starting at the end, and if any
407 /// of them return `true`, then `rfind()` returns [`Some(element)`]. If they all return
408 /// `false`, it returns [`None`].
409 ///
410 /// `rfind()` is short-circuiting; in other words, it will stop processing
411 /// as soon as the closure returns `true`.
412 ///
413 /// Because `rfind()` takes a reference, and many iterators iterate over
414 /// references, this leads to a possibly confusing situation where the
415 /// argument is a double reference. You can see this effect in the
416 /// examples below, with `&&x`.
417 ///
418 /// [`Some(element)`]: Some
419 ///
420 /// # Examples
421 ///
422 /// Basic usage:
423 ///
424 /// ```
425 /// let a = [1, 2, 3];
426 ///
427 /// assert_eq!(a.into_iter().rfind(|&x| x == 2), Some(2));
428 /// assert_eq!(a.into_iter().rfind(|&x| x == 5), None);
429 /// ```
430 ///
431 /// Iterating over references:
432 ///
433 /// ```
434 /// let a = [1, 2, 3];
435 ///
436 /// // `iter()` yields references i.e. `&i32` and `rfind()` takes a
437 /// // reference to each element.
438 /// assert_eq!(a.iter().rfind(|&&x| x == 2), Some(&2));
439 /// assert_eq!(a.iter().rfind(|&&x| x == 5), None);
440 /// ```
441 ///
442 /// Stopping at the first `true`:
443 ///
444 /// ```
445 /// let a = [1, 2, 3];
446 ///
447 /// let mut iter = a.iter();
448 ///
449 /// assert_eq!(iter.rfind(|&&x| x == 2), Some(&2));
450 ///
451 /// // we can still use `iter`, as there are more elements.
452 /// assert_eq!(iter.next_back(), Some(&1));
453 /// ```
454 #[inline]
455 #[stable(feature = "iter_rfind", since = "1.27.0")]
456 fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item>
457 where
458 Self: Sized,
459 P: [const] FnMut(&Self::Item) -> bool + [const] Destruct,
460 Self::Item: [const] Destruct,
461 {
462 #[inline]
463 #[rustc_const_unstable(feature = "const_iter", issue = "92476")]
464 const fn check<T>(
465 mut predicate: impl [const] FnMut(&T) -> bool + [const] Destruct,
466 ) -> impl [const] FnMut((), T) -> ControlFlow<T> + [const] Destruct
467 where
468 T: [const] Destruct,
469 {
470 const move |(), x| {
471 if predicate(&x) { ControlFlow::Break(x) } else { ControlFlow::Continue(()) }
472 }
473 }
474
475 self.try_rfold((), check(predicate)).break_value()
476 }
477}
478
479#[stable(feature = "rust1", since = "1.0.0")]
480impl<'a, I: DoubleEndedIterator + ?Sized> DoubleEndedIterator for &'a mut I {
481 fn next_back(&mut self) -> Option<I::Item> {
482 (**self).next_back()
483 }
484 fn advance_back_by(&mut self, n: usize) -> Result<(), NonZero<usize>> {
485 (**self).advance_back_by(n)
486 }
487 fn nth_back(&mut self, n: usize) -> Option<I::Item> {
488 (**self).nth_back(n)
489 }
490 fn rfold<B, F>(self, init: B, f: F) -> B
491 where
492 F: FnMut(B, Self::Item) -> B,
493 {
494 self.spec_rfold(init, f)
495 }
496 fn try_rfold<B, F, R>(&mut self, init: B, f: F) -> R
497 where
498 F: FnMut(B, Self::Item) -> R,
499 R: Try<Output = B>,
500 {
501 self.spec_try_rfold(init, f)
502 }
503}
504
505/// Helper trait to specialize `rfold` and `rtry_fold` for `&mut I where I: Sized`
506trait DoubleEndedIteratorRefSpec: DoubleEndedIterator {
507 fn spec_rfold<B, F>(self, init: B, f: F) -> B
508 where
509 F: FnMut(B, Self::Item) -> B;
510
511 fn spec_try_rfold<B, F, R>(&mut self, init: B, f: F) -> R
512 where
513 F: FnMut(B, Self::Item) -> R,
514 R: Try<Output = B>;
515}
516
517impl<I: DoubleEndedIterator + ?Sized> DoubleEndedIteratorRefSpec for &mut I {
518 default fn spec_rfold<B, F>(self, init: B, mut f: F) -> B
519 where
520 F: FnMut(B, Self::Item) -> B,
521 {
522 let mut accum = init;
523 while let Some(x) = self.next_back() {
524 accum = f(accum, x);
525 }
526 accum
527 }
528
529 default fn spec_try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R
530 where
531 F: FnMut(B, Self::Item) -> R,
532 R: Try<Output = B>,
533 {
534 let mut accum = init;
535 while let Some(x) = self.next_back() {
536 accum = f(accum, x)?;
537 }
538 try { accum }
539 }
540}
541
542impl<I: DoubleEndedIterator> DoubleEndedIteratorRefSpec for &mut I {
543 impl_fold_via_try_fold! { spec_rfold -> spec_try_rfold }
544
545 fn spec_try_rfold<B, F, R>(&mut self, init: B, f: F) -> R
546 where
547 F: FnMut(B, Self::Item) -> R,
548 R: Try<Output = B>,
549 {
550 (**self).try_rfold(init, f)
551 }
552}